/*
 * Copyright (c) 2012, Markus Weber All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without modification, are
 * permitted provided that the following conditions are met:
 * 
 * Redistributions of source code must retain the above copyright notice, this list of
 * conditions and the following disclaimer. Redistributions in binary form must reproduce the
 * above copyright notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the author nor the names of its contributors may be used to endorse or
 * promote products derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 */
package de.dfki.graph;

import java.lang.reflect.Type;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

import org.apache.log4j.Logger;
import org.jgrapht.graph.DirectedMultigraph;

/**
 * A labeled graph consists of a 7-tuple G = (V, E, Lv, Le, mu, v, sigma),
 * where: 
 *   - V is a set of vertices, 
 *   - E is a set of edges, 
 *   - Lv : is a set of labels for the vertices, 
 *   - Le : is a set of labels for the edges, 
 *   - mu : V -> Lv is a function which assigns a label to the vertices,
 *   - v : E -> Le is a function which assigns a label to the edges, 
 *    - sigma : Lv elem N is a function which assigns a weight to the label of the edges,
 *
 *  and a binary relation <= which defines a well-founded total order on the 
 *  weights of the labels: for all x, y in Lv : sigma(x) <= sigma(y) AND sigma(y)
 *  <= sigma(x)
 *
 *
 * @author Markus Weber
 *
 */
public class LabeledGraph extends DirectedMultigraph<LabeledVertex<? extends LabelType<?>>, LabeledEdge<?>> implements
        Iterable<LabeledVertex<?>> {

    /**
     * Serial id
     */
    private static final long serialVersionUID = 5827953485264163101L;
    /**
     * Logger
     */
    private Logger log = Logger.getLogger(LabeledGraph.class);
    /**
     * Name of the graph.
     */
    private final String name;
    /**
     * Mapping
     */
    private ConcurrentMap<String, Set<LabeledVertex<? extends LabelType<?>>>> typeMap;
    /**
     * 
     */
    private ConcurrentMap<String, Byte> weights;
    /**
     * ID lookup
     */
    private ConcurrentMap<String, LabeledVertex<? extends LabelType<?>>> idMap;
    /**
     * Index
     */
    private int IDsequence = 0;
    /*
     * Assigned weight
     */
    private byte weightSequence = 0;
    /**
     * Lock
     */
    private final Object lock = new Object();
    
    /**
     * Label order
     */
    private WellDefinedOrder order;
    /**
     * Mode of the edge.
     *
     * @author Markus Weber
     *
     */
    public enum EdgeMode {
        DIRECTED, INDIRECTED
    }

    /**
     * Creates a labeled graph.
     *
     * @param image
     * @param name
     */
    public LabeledGraph(final String name, WellDefinedOrder order) {
	super((Class<? extends LabeledEdge<? extends LabelType<?>>>) LabeledGraph.getClass(LabeledEdge.class));
        this.name = name;
        this.order = order;
        this.typeMap = new ConcurrentHashMap<String, Set<LabeledVertex<?>>>();
        this.idMap = new ConcurrentHashMap<String, LabeledVertex<?>>();
        this.weights = new ConcurrentHashMap<String, Byte>();

    }

    /**
     * Creates a labeled vertex and adds the vertex to the graph.
     *
     * @param label
     * @return
     */
    public <T extends LabelType<?>> LabeledVertex<T> createVertex(T label) {
        synchronized (lock) {
            return createVertex(Integer.toString(IDsequence++), label);
        }
    }

    /**
     * Returns the vertex by ID.
     *
     * @param id
     * @return
     */
    @SuppressWarnings("unchecked")
    public <T extends LabelType<?>> LabeledVertex<T> getVertexByID(final String id) {
        return (LabeledVertex<T>) this.idMap.get(id);
    }

    /**
     * Returns the label map
     *
     * @return
     */
    public Map<String, Set<LabeledVertex<?>>> getLabelMap() {
        return typeMap;
    }

    /**
     * Creates a labeled vertex and adds the vertex to the graph.
     *
     * @param id
     * @param label
     * @return
     */
    public <T extends LabelType<?>> LabeledVertex<T> createVertex(String ID,
            T label) {
        synchronized (lock) {
            LabeledVertex<T> v = new LabeledVertex<T>(label, ID);
            this.addVertex(v);
            byte w = 0;
            Set<LabeledVertex<?>> set;
            if (this.typeMap.containsKey(label.toString())) {
                set = this.typeMap.get(label.toString());
                w = this.weights.get(label.toString());
            } else {
                set = new HashSet<LabeledVertex<?>>();
                this.typeMap.put(label.toString(), set);
                this.weights.put(label.toString(), this.weightSequence);
                w = weightSequence;
                this.weightSequence++;
                log.debug("New label type [value]=" + label.getValue());
            }
            label.updateWeight(w);
            this.idMap.put(ID, v);
            set.add(v);
            return v;
        }
    }

    /**
     * Returns entities of a certain type.
     *
     * @param t
     * @return
     */
    public Set<LabeledVertex<?>> getVertexes(LabelType<?> t) {
        return this.typeMap.get(t.toString());
    }

    /**
     * Adding an edge with vertex ids.
     *
     * @param iD_source
     * @param iD_target
     */
    public <T extends LabelType<?>> LabeledEdge<T> addEdge(String iD_source, String iD_target, T label) {
        return (LabeledEdge<T>) this.addEdge(this.getVertexByID(iD_source), this.getVertexByID(iD_target), label);
    }

    /**
     * Adds an edge with a specific label.
     *
     * @param sourceVertex
     * @param targetVertex
     * @param label
     * @return
     */
    public <T extends LabelType<?>> LabeledEdge<T> addEdge(LabeledVertex<?> sourceVertex,
            LabeledVertex<?> targetVertex, T label) {
        if (sourceVertex != null && targetVertex != null) {
            @SuppressWarnings("unchecked")
            LabeledEdge<T> e = (LabeledEdge<T>) super.addEdge(sourceVertex, targetVertex);
            e.setLabel(label);
            return e;
        }
        return null;
    }
    
    /**
     * Returns the name of the graph.
     *
     * @return the name
     */
    public String getName() {
        return name;
    }

    /*
     * (non-Javadoc)
     *
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj) // same reference
        {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        LabeledGraph other = (LabeledGraph) obj;
        return other.name.equals(obj);
    }

    @Override
    public int hashCode() {
        int hash = 5;
        hash = 59 * hash + (this.name != null ? this.name.hashCode() : 0);
        return hash;
    }

    /*
     * (non-Javadoc)
     *
     * @see java.lang.Iterable#iterator()
     */
    @Override
    public Iterator<LabeledVertex<? extends LabelType<?>>> iterator() {
        List<LabeledVertex<? extends LabelType<?>>> list = new ArrayList<LabeledVertex<? extends LabelType<?>>>(this.vertexSet());
        Collections.sort(list, order);
        return list.iterator();
    }



    /**
     * Returns the maximum number of vertices with the same label.
     *
     * @return n_max
     */
    public int maxSameLabels() {
        int max = 0;
        synchronized (lock) {
            for (String s : typeMap.keySet()) {
                if (typeMap.get(s).size() > max) {
                    max = typeMap.get(s).size();
                }
            }
        }
        return max;
    }

    /**
     * Returns the number of vertices.
     *
     * @return
     */
    public int numberOfVertices() {
        return this.vertexSet().size();
    }

    /**
     * Returns the number of different labels.
     *
     * @return
     */
    public int numberOfLabels() {
        return this.typeMap.size();
    }
    
    
  /**
   * Get the underlying class for a type, or null if the type is a variable type.
   * @param type the type
   * @return the underlying class
   */
  public static Class<?> getClass(Type type) {
    if (type instanceof Class) {
      return (Class) type;
    }
    return null;
  }

}
